{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Recursion, Memoization and Dynamic Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Remember how we talk about using recursion and dynamic programming. One interesting thing to do is to implement the solution to a common problem called Fibonnaci numbers on these two styles and compare the compute time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The Fibonacci series looks something like: `0, 1, 1, 2, 3, 5, 8, 13, 21 …` and so on. Any person can quickly notice the pattern. `f(n) = f(n-1) + f(n-2)` So, let's walk through a recursive implementation that solves this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n < 2:\n",
    "        return n\n",
    "    return fib(n-2) + fib(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 296 ms, sys: 0 ns, total: 296 ms\n",
      "Wall time: 295 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time fib(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Now, the main problem of this algorithm is that we are computing some of the subproblems more than once. For instance, to compute fib(4) we would compute fib(3) and fib(2). However, to compute fib(3) we also have to compute fib(2). Say hello to memoization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "A technique called memoization we are cache the results of previously computed sub problems to avoid unnecessary computations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "m = {}\n",
    "def fibm(n):\n",
    "    if n in m:\n",
    "        return m[n]\n",
    "    m[n] = n if n < 2 else fibm(n-2) + fibm(n-1)\n",
    "    return m[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 17.6 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time fibm(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "But the question is, can we do better than this? The use of the array is helpful, but when calculating very large numbers, or perhaps on memory contraint environments it might not be desirable. This is where Dynamic Programming fits the bill."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "In DP we take a bottom-up approach. Meaning, we solve the next Fibonacci number we can with the information we already have."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def fibdp(n):\n",
    "    if n == 0: return 0\n",
    "    prev, curr = (0, 1)\n",
    "    for i in range(2, n+1):\n",
    "        newf = prev + curr\n",
    "        prev = curr\n",
    "        curr = newf\n",
    "    return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 6.44 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "832040"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time fibdp(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "In this format, we don’t need to recurse or keep up with the memory intensive cache dictionary. These, add up to an even better performance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's now give it a try with factorials. Remember `4! = 4 * 3 * 2 * 1 = 24`. Can you give it try?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def factr(n):\n",
    "    if n < 3:\n",
    "        return n\n",
    "    return n * factr(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 43.2 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "265252859812191058636308480000000"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time factr(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "m = {}\n",
    "def factm(n):\n",
    "    if n in m:\n",
    "        return m[n]\n",
    "    m[n] = n if n < 3 else n * factr(n - 1)\n",
    "    return m[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 47.2 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "265252859812191058636308480000000"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time factm(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def factdp(n):\n",
    "    if n < 3: return n\n",
    "    fact = 2\n",
    "    for i in range(3, n + 1):\n",
    "        fact *= i\n",
    "    return fact"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 7.87 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "265252859812191058636308480000000"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time factdp(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's think of a slightly different problem. Imagine that you want to find the cheapest way to go from city A to city B, but when you are about to buy your ticket, you see that you could hop in different combinations of route and get a much cheaper price than if you go directly. How do you efficiently calculate the best possible combination of tickets and come up with the cheapest route? We will start with basic recursion and work on improving it until we reach dynamic programming.\n",
    "\n",
    "For this last problem in dynamic programming, create 2 functions that calculates the cheapest route from city A to B. I will give you the recursive solution, you will build one with memoization and the one with dynamic programming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Utility function to get fares between cities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "def get_fares(n_cities, max_fare):\n",
    "    np.random.seed(123456)\n",
    "    fares = np.sort(np.random.random((n_cities, n_cities)) * max_fare).astype(int)\n",
    "    for i in range(len(fares)):\n",
    "        fares[i] = np.roll(fares[i], i + 1)\n",
    "    np.fill_diagonal(fares, 0)\n",
    "    for i in range(1, len(fares)):\n",
    "        for j in range(0, i):\n",
    "            fares[i][j] = -1\n",
    "    return fares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try it out with 4 cities and random fares with a max of 1000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0, 126, 260, 897],\n",
       "       [ -1,   0,  50, 376],\n",
       "       [ -1,  -1,   0, 123],\n",
       "       [ -1,  -1,  -1,   0]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n_cities = 4\n",
    "max_fare = 1000\n",
    "fares = get_fares(n_cities, max_fare)\n",
    "fares[1][2] = 50\n",
    "fares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the recursive solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def cheapestr(s, d, c):\n",
    "    if s == d or s == d - 1:\n",
    "        return c[s][d]\n",
    "    \n",
    "    cheapest = c[s][d]\n",
    "    for i in range(s + 1, d):\n",
    "        tmp = cheapestr(s, i, c) + cheapestr(i, d, c)\n",
    "        cheapest = tmp if tmp < cheapest else cheapest\n",
    "    return cheapest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 68.7 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "299"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cheapestr(0, len(fares[0]) - 1, fares)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, you build the memoization one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "m = {}\n",
    "def cheapestm(s, d, c):\n",
    "    \"\"\" YOU WRITE THIS FUNCTION \"\"\"\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 22.6 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "299"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cheapestm(0, len(fares[0]) - 1, fares)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Faster, you see?\n",
    "\n",
    "Now, do the dynamic programming version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def cheapestdp(s, d, c):\n",
    "    \"\"\" YOU WRITE THIS FUNCTION \"\"\"\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 61.5 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "299"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cheapestdp(0, len(fares[0]) - 1, fares)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's now try with a larger example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 337,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0, 123, 126, 129, 228, 260, 336, 352, 373, 376, 447, 451, 543,\n",
       "        776, 820, 840, 859, 897],\n",
       "       [ -1,   0,  37,  61, 137, 146, 235, 245, 340, 343, 405, 574, 589,\n",
       "        590, 594, 753, 852, 861],\n",
       "       [ -1,  -1,   0,  16,  99, 117, 170, 199, 274, 342, 394, 401, 414,\n",
       "        462, 481, 595, 610, 641],\n",
       "       [ -1,  -1,  -1,   0,  94,  95, 134, 138, 155, 433, 471, 497, 560,\n",
       "        630, 639, 683, 732, 758],\n",
       "       [ -1,  -1,  -1,  -1,   0,  85, 140, 149, 329, 370, 386, 395, 477,\n",
       "        544, 562, 566, 619, 634],\n",
       "       [ -1,  -1,  -1,  -1,  -1,   0,  29,  30,  44, 113, 187, 207, 247,\n",
       "        249, 249, 356, 409, 630],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,   0,  22,  60, 168, 216, 277, 279,\n",
       "        372, 419, 449, 606, 690],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,   0,  30,  36, 273, 321, 355,\n",
       "        415, 419, 421, 497, 500],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,   0,  19, 123, 400, 412,\n",
       "        418, 535, 547, 559, 591],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,   0, 110, 120, 140,\n",
       "        204, 220, 395, 454, 488],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,   0,  87, 169,\n",
       "        219, 257, 312, 487, 527],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,   0,   7,\n",
       "         11,  22, 244, 250, 281],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,   0,\n",
       "         10, 116, 123, 259, 287],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,\n",
       "          0,  22,  93, 109, 236],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,\n",
       "         -1,   0,  29, 157, 185],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,\n",
       "         -1,  -1,   0,  18,  78],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,\n",
       "         -1,  -1,  -1,   0,   4],\n",
       "       [ -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1,\n",
       "         -1,  -1,  -1,  -1,   0]])"
      ]
     },
     "execution_count": 337,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n_cities = 18 # this will take a little before 20 seconds. Try not to make it any larger :)\n",
    "max_fare = 1000\n",
    "fares = get_fares(n_cities, max_fare)\n",
    "fares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 338,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 18.3 s, sys: 6.67 ms, total: 18.3 s\n",
      "Wall time: 18.4 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "480"
      ]
     },
     "execution_count": 338,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cheapestr(0, len(fares[0]) - 1, fares)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 339,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 14.7 s, sys: 3.33 ms, total: 14.7 s\n",
      "Wall time: 14.7 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "480"
      ]
     },
     "execution_count": 339,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cheapestm(0, len(fares[0]) - 1, fares)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 340,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 75.8 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "480"
      ]
     },
     "execution_count": 340,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time cheapestdp(0, len(fares[0]) - 1, fares)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "BAAAAAM! See how much faster dynamic programming is?\n",
    "\n",
    "Well, there you have it!!! This is the power of dynamic programming.\n",
    "\n",
    "As mentioned in the tutorials, reinforcement learning leverages the power of dynamic programming in many algorithms. Value Iteration, Q-Learning, etc have a similar take on calculation. The bottom line is to think sequentially instead of recursively. And bottom-up instead of top-down. Let's continue this journey."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
